// 轮转数组

// 1. 额外空间直接拷贝
// 2. 翻转整个数组再内部翻转
// 3. 环状替换 

// 环状替换
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size();
        // 环状个数 -> k和size的最大公约数
        int count = gcd(size, k);
        for(int i = 0; i < count; ++i)
        {
            int preValue = nums[i];
            int curIndex = i;
            int beginIndex = i;
            do
            {
                curIndex = (curIndex + k) % size; 
                int tmp = nums[curIndex];
                nums[curIndex] = preValue;
                preValue = tmp;
            }while(beginIndex != curIndex);
        }
    }
};


// 翻转整个数组再内部翻转
class Solution {
public:
    void reverse(vector<int>& nums, const int& left, const int& right)
    {
        int begin = left, end = right;
        while(begin < end)
        {
            swap(nums[begin], nums[end]);
            ++begin;
            --end;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int size = nums.size();
        k %= size;
        reverse(nums, 0, size - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, size - 1);
    }
};
